/**
 * 最后一个石头的重量
 * 有一堆石头，每块石头的重量都是正整数。
 *
 * 每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为x 和y，且x <= y。那么粉碎的可能结果如下：
 *
 * 如果x == y，那么两块石头都会被完全粉碎；
 * 如果x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
 * 最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
 *https://leetcode.cn/problems/last-stone-weight/
 *思路：将所有石头的重量放入最大堆中。每次依次从队列中取出最重的两块石头 a 和 b，必有 a≥b。如果 a>b，则将新石头 a-b 放回到最大堆中；
 * 如果 a=b，两块石头完全被粉碎，因此不会产生新的石头。重复上述操作，直到剩下的石头少于 2 块。
 *
 * 最终可能剩下 1块石头，该石头的重量即为最大堆中剩下的元素，返回该元素；也可能没有石头剩下，此时最大堆为空，返回 00。
 *
 *
 *
 *
 */

import java.util.Comparator;
import java.util.PriorityQueue;

class Intcmp implements Comparator<Integer> {//idea默认是小跟堆，要重写比较器，才是大根堆

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    }
public class LastStoneWeight {
     
    public int lastStoneWeight(int[] stones) {
        Intcmp intcmp=new Intcmp();
        PriorityQueue<Integer> qu=new PriorityQueue<>(intcmp);
        for (int stone:stones) {
            qu.offer(stone);
        }
        while(qu.size()>1){
            int a=qu.poll();
            int b=qu.poll();
            if(a>b){
                qu.offer(a-b);
            }
        }
        return qu.isEmpty()?0:qu.poll();
    }
}